// 创建更好的散列函数
// 之前实现的 “lose lose” 散列函数并不是一个表现良好的散列函数
// 因为它会产生太多的冲突
// 一个表现良好的散列函数是由几个方面构成的：
// 插入和检索元素的时间(即性能)
// 当然也包括较低的冲突可能性

var djb2HashCode = function(key){
	var hash = 5381;

	for(var i = 0; i < key.length; i++){
		hash = hash * 33 + key.charCodeAt(i);
	}

	return hash % 1013;
}

// 上面的散列函数初始化一个hash变量并赋值为一个质数(大多数实现都使用5381)
// 然后迭代参数key
// 将hash与33相乘(用来当做一个魔力数)，并和当前迭代到的字符ASCII码值相加
// 最后得到的和与另一个随机质数(比我们认为的散列表的大小要大，此处认为散列大小为1000)求余
// 这并不是最好的散列函数，但这是最被社区推荐的散列函数之一。

function HashTable(){
	var table = [];

	var ValuePair = function(key, value){
		this.key = key;
		this.value = value;
	}

	var djb2HashCode = function(key){
		var hash = 5381;

		for(var i = 0; i < key.length; i++){
			hash = hash * 33 + key.charCodeAt(i);
		}

		return hash % 1013;
	}

	this.put = function(key, value){
		var position = djb2HashCode(key);

		if(table[position] == undefined){
			table[position] = new ValuePair(key, value);
		} else {
			var index = ++position;
			while(table[index] != undefined && table[index].key !== key){
				index++;
			}
			if(table[index].key === key) { // 如果已经添加过该key值，只改变value值即可
				table[index].value = value;
			} else {
				table[index] = new ValuePair(key, value);
			}
		}
	}

	this.get = function(key){
		var position = djb2HashCode(key);

		if(table[position] != undefined){
			if(table[position].key === key){
				return table[position].value;
			} else {
				var index = ++position;
				while(table[index] === undefined || table[index].key !== key){
					// table[index] === undefined 可能是由于remove方法造成的
					index++;
				}
				if(table[index].key === key){
					return table[index].value;
				}
			}
		}
		return undefined
	}

	this.remove = function(key){
		var position = djb2HashCode(key);

		if(table[position] != undefined){
			if(table[position].key === key){
				table[position] = undefined;
				return true;
			}
			var index = ++position;
			while(table[index] === undefined || table[index].key !== key){
				index++;
			}
			if(table[index].key === key){
				table[index] = undefined;
				return true;
			}
		}
		return false;
	}
}